﻿#pragma once
#include <iostream>
#include<vector>
#include<unordered_map>
#include<assert.h>
#include<thread>
#include<mutex>

#include<algorithm>
#include"ObjectPool.hpp"
#ifdef _WIN32
#include<Windows.h>
#else
//。。。。
#endif // _WIN32

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;//最大thread cache申请内存大小
static const size_t MAX_LIST_NUM = 208;//最大central list个数
static const size_t MAX_PAGE_NUM = 129;//最大的pagecache的申请页数
static const size_t PAGE_SHIFT = 13;//用于 << >> ,让页号和内存地址直接的转移.(左移13位相等于乘以2的13次方 8k)
//这里条件编译是为了在win64时 在OS给分配页时，因为win64是64位比特位，所以数字会很多，2的64次方，如果用int存不下
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef int PAGE_ID;
#else
//.....
#endif // _WIN64

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	//在windows下申请几页内存
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	//在linux下
#endif // _WIN32
	if(ptr == nullptr)throw std::bad_alloc();
	return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}
inline void*& NextObj(void* obj)
{
	return *(void**)obj;
}

class FreeList
{
public:

	//进表
	//采用头插头删出入法，时间复杂度都是o1；
	//push和pop不用考虑大小因为能进来这里说明一定是调用了这个大小的_freelist
	bool Empty()
	{
		return _freelist == nullptr;
	}
	void push(void* obj)
	{
		assert(obj);//空节点没用。
		//还回节点
		NextObj(obj) = _freelist;
		_freelist = obj;
		_size++;
	}
	//出表
	void* pop()
	{
		assert(_freelist);//freelist为空，那就说明并没有节点，你调用allocate时要考虑是否有节点
		//拿出节点
		void* obj = _freelist;
		_freelist = NextObj(_freelist);
		_size--;
		return obj;
	}
	void pushRange(void* start, void* end, size_t n)
	{
		//也是头插
		//把屁股插头上，然后再把头连头
		assert(start && end);
		NextObj(end) = _freelist;
		//std::cout << NextObj(end) << std::endl;
		_freelist = start;
		_size += n;
	}
	//start end 是 输入输出型参数，要让pop出去的地址被外层都拿到；
	void popRange(void*& start, void*& end, size_t n)
	{
		assert(_freelist);
		assert(n <= _size);
		start = _freelist;
		end = start;
		for (int i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		//将这一段彻底从_freelist中分离出来
		_freelist = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	size_t& Maxsize()
	{
		return _Maxsize;
	}
	size_t& size()
	{
		return _size;
	}
private:
	size_t _size = 0;//记录链表中的个数
	void* _freelist = nullptr;//链表的头结点
	size_t _Maxsize = 1;//记录此时一次分配多少个小块节点给thread，和计算此时threadcache中能剩下的最大数量
};
//这个类就是用来管理Size对齐和映射位置的
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎⽚浪费 对齐规则
	// [1,128] 8byte对⻬					freelist[0,16)
	// [128+1,1024] 16byte对⻬				freelist[16,72)
	// [1024+1,81024] 128byte对⻬			freelist[72,128)
	// [8*1024+1,641024] 1024byte对⻬		freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬	freelist[184,208)
	static size_t _RoundUp(size_t bytes,size_t align)//找到在那一层的哪一个队伍
	{
		//1.后面的align - 1，根据上面的对齐规则，发现基本都是2的次方。-1就可以把二进制中这一位后面的0全变为1，之后再取反，前面的全变为1,
		//2.bytes + align - 1：想不出来，总之要用反证法
		//如果想不起来那就用自己的思路加减乘除来解决，但用比特位运算会更快
		return (((bytes)+align - 1) & ~(align - 1));//这些自己想不出来的，证明的话就用例子去反证即可比如用1 8,10 16.
	}
	static size_t RoundUp(size_t size)//向上对齐
	{
		assert(size);
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else return _RoundUp(size, 1 << PAGE_SHIFT);
	}
	static size_t _Index(size_t bytes,size_t align_shift)
	{
		//1.align_shift,是第几个比特位，对齐数的1在第几个比特位
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	static size_t Index(size_t size)//确定桶的位置
	{
		//现在已经有round了，要求的是具体在哪个桶
		assert(size <= MAX_BYTES);
		static int group_arr[] = { 16,56,56,56 };
		//1.确定在哪个层
		if (size <= 128)
		{
			return _Index(size,3);
		}
		else if (size <= 1024)
		{
			//减去前一个值的原因是，接下来要找的是在下一个层
			//加上前一层里总共的小队数，_Index算的是在这一层的第几个小队；
			return _Index(size-128,4)+group_arr[0];
		}
		else if (size <= 8*1024)
		{
			return _Index(size - 1024, 7) + group_arr[0] + group_arr[1];
		}
		else if (size <= 64*1024)
		{
			return _Index(size - 8 * 1024, 10) + group_arr[0] + group_arr[1] + group_arr[2];
		}
		else if (size <= 256 * 1024)
		{
			return _Index(size-64 * 1024,13) + group_arr[0] + group_arr[1] + group_arr[2] + group_arr[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}
	//根据需求大小一次从central中拿多少个小内存块
	static  size_t NummoveSize(size_t size)
	{
		//设置上下限
		assert(size > 0);
		int num = MAX_BYTES / size;//拿几个
		if (num < 2) return 2;
		if (num > 512)return 512;
		return num;
	}
	static inline size_t NummovePage(size_t size)
	{
		assert(size >0);
		//需要的页数根据size
		size_t n = NummoveSize(size);//这里只是看看可能需要分配几个个小块；
		size_t npage = n * size;//这里算出这n个小块的总大小；
		npage >>= PAGE_SHIFT;//除以8k，算出的是需要分配的页数。

		if (npage == 0) npage = 1;
		return npage;
	}
};
class Span
{
public:
	PAGE_ID _pageId = 0; // ⼤块内存起始⻚的⻚号
	size_t _n = 0; // ⻚的数量
	Span* _next = nullptr; // 双向链表的结构
	Span* _prev = nullptr;
	size_t _objSize = 0; // 切好的⼩对象的⼤⼩
	size_t _useCount = 0; // 切好⼩块内存，被分配给thread cache的计数
	void* _freeList = nullptr; // 切好的⼩块内存的⾃由链表
	bool _isUse = false; // 是否在被使⽤
};
class SpanList//有最基本的插入和取出操作。
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	//加一个span节点
	void Pushfront(Span*& newspan)
	{
		Insert(Begin(), newspan);
	}
	//去除一个span节点
	Span* Popfront()
	{
		return Erase(Begin());
	}
	void Insert(Span* pos, Span* newspan)
	{
		assert(pos && newspan);
		Span* next = pos->_next;
		pos->_next = newspan;
		newspan->_prev = pos;
		newspan->_next = next;
		next->_prev = newspan;
	}
	Span* Erase(Span* pos)
	{
		assert(pos);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		next->_prev = prev;
		prev->_next = next;
		return pos;
	}
private:
	Span* _head;//头结点
public:
	std::mutex _mutex;
};